|
|
Algoritmus pro pevné body homomorfismů na slovech
Matocha, Vojtěch ; Holub, Štěpán (vedoucí práce) ; Žemlička, Jan (oponent)
V předložené práci studuji polynomiální algoritmus, který pro dané slovo rozhoduje, zda je pevným bodem nějakého netriviálního homomorfismu. Součástí práce je zpřesněný odhad složitosti, algoritmus v nejhorším případě pracuje v čase O(m · n), kde n značí délku slova a m velikost použité abecedy. V práci se dále zabývám problémem union-find, který je stěžejní součástí popisovaného algoritmu, a s odhadem jeho složitosti související Ackermannovou funkcí. V práci jsou shrnuty používané metody a důkazy jejich složitostí a je popsán postup, kterým lze řešit speciální případ union-find vyskytující se ve zkoumaném algoritmu. Následuje konkrétní implementace algoritmu, jejíž testovaná složitost odpovídá zpřesněnému odhadu. Součástí práce je také vizualizace chodu algoritmu na konkrétních vstupech.
|
|
|
Toky cestami omezené délky
Altmanová, Kateřina ; Kolman, Petr (vedoucí práce) ; Pangrác, Ondřej (oponent)
V bakalářské práci se zabýváme problémem k-omezeného toku, a tedy toku, který lze dekomponovat na cesty délky nejvýše k. Podáváme přehled o známých výsledcích v této oblasti a zmiňujeme také problém k-omezeného řezu, což je množina hran z tokové sítě, která po odebrání z tokové sítě způsobí, že nee- xistuje v takto pozměněné síti k-omezený tok. Hlavním cílem práce je detailní prozkoumání článku The Maximum k-flow in a Network od autorů V. Kou- bek a A. Říha, publikovaného ve sborníku konference Mathematical Foundations of Coputer Science 1981, str. 389-397 a podání vysvětlení složitých pasáží a do- plnění vynechaných důkazů. Cíl doplnit chybějící důkazy, v této práci naplněný není. Ukázalo, že v citovaném článku mají autoři zásadní chybu. Místo doka- zování vynechaných důkazů se zaměřujeme na popsání problému, proč původní algoritmus nefunguje. 1
|
|
|
Probabilistické algoritmy pro prvočíselnost
Tejkalová, Natálie ; Švejdar, Vítězslav (vedoucí práce) ; Glivický, Petr (oponent)
Ačkoli v poslední době byla pozornost upřena především na nový deterministický algoritmus pro testování prvočíselnosti AKS, pravděpodobnostní algoritmy zůstávají efektivním nástrojem pro testování prvočíselnosti. Naše práce se věnuje převážně dvěma nejznámějším probabilistickým algoritmům pro testování prvočíselnosti. Podrobně popisuje princip a důkaz správnosti Solovay- Strassenova a Rabin-Millerova algoritmu. Kromě toho se také pokouší dívat na problematiku pravděpodobnostních testů obecněji. Je představena definice probabilistického algoritmu a různé třídy složitosti odpovídající Monte Carlo či Las Vegas algoritmům. Kromě čistě matematické teorie naznačíme i filosofické aspekty, nad kterými je třeba se při používání pravděpodobnostní metody zamýšlet. Powered by TCPDF (www.tcpdf.org)
|
|
|
Algoritmus pro pevné body homomorfismů na slovech
Matocha, Vojtěch ; Holub, Štěpán (vedoucí práce) ; Žemlička, Jan (oponent)
V předložené práci studuji polynomiální algoritmus, který pro dané slovo rozhoduje, zda je pevným bodem nějakého netriviálního homomorfismu. Součástí práce je zpřesněný odhad složitosti, algoritmus v nejhorším případě pracuje v čase O(m · n), kde n značí délku slova a m velikost použité abecedy. V práci se dále zabývám problémem union-find, který je stěžejní součástí popisovaného algoritmu, a s odhadem jeho složitosti související Ackermannovou funkcí. V práci jsou shrnuty používané metody a důkazy jejich složitostí a je popsán postup, kterým lze řešit speciální případ union-find vyskytující se ve zkoumaném algoritmu. Následuje konkrétní implementace algoritmu, jejíž testovaná složitost odpovídá zpřesněnému odhadu. Součástí práce je také vizualizace chodu algoritmu na konkrétních vstupech.
|
host ::
RSS.